package com.lfg.leetcode.leetcode500;

import com.alibaba.fastjson.JSON;

import java.util.*;

public class No632smallestRange {
    public static void main(String[] args) {
//        List<List<Integer>> list = new ArrayList<>();
//        list.add(new ArrayList<>(Arrays.asList(4, 10, 15, 24, 26)));
//        list.add(new ArrayList<>(Arrays.asList(0, 9, 12, 20)));
//        list.add(new ArrayList<>(Arrays.asList(5, 18, 22, 30)));
//        int[] ret = smallestRange(list);
//        System.out.println("[" + JSON.toJSONString(ret) + "]");


        List<List<Integer>> list2 = new ArrayList<>();
        list2.add(new ArrayList<>(Arrays.asList(-5, -4, -3, -2, -1)));
        list2.add(new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5)));
        int[] ret2 = smallestRange(list2);
        System.out.println("[" + JSON.toJSONString(ret2) + "]");

    }


    public static int[] smallestRange(List<List<Integer>> nums) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        Set<Integer> all = new HashSet<>();
        for (int position = 0; position < nums.size(); position++) {
            List<Integer> l = nums.get(position);
            all.addAll(l);
            for (int i : l) {
                Set<Integer> list = map.get(i);
                if (list == null) {
                    list = new HashSet<>();
                    map.put(i, list);
                }
                list.add(position);
            }
        }
        List<Integer> list = new ArrayList<>(all);
        Collections.sort(list);
        int left = 0;

        int[] ret = new int[]{list.get(0), list.get(list.size() - 1)};

        int[] cnt = new int[nums.size()];
        int total = 0;
        for (int i = 0; i < list.size(); i++) {

            Set<Integer> set = map.get(list.get(i));
            for (Integer n : set) {
                cnt[n]++;
                if (cnt[n] == 1) {
                    total++;
                }
            }

            while (total == nums.size()) {
                if (list.get(i) - list.get(left) <= ret[1] - ret[0]) {
                    ret[0] = list.get(left);
                    ret[1] = list.get(i);
                }
                if (ret[1] - ret[0] == 0) {
                    return ret;
                }
                set = map.get(list.get(left));
                for (Integer n : set) {
                    cnt[n]--;
                    if (cnt[n] == 0) {
                        total--;
                    }
                }
                left++;
            }

        }
        return ret;
    }


}
